/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function (board, words) {
  const trie = new Trie(); // 生成一个新的字典树
  const dxys = [
    [0, -1],
    [-1, 0],
    [0, 1],
    [1, 0],
  ]; // 方向数组
  const xLen = board.length // x方向的长度
  let yLen = board[0].length // y方向的长度
  let visited = {} // 记录访问过的
  const ret = [] // 结果数组
  for (let word of words) {
    trie.insert(word) // 加入字典树
  }
  const dfs = (x, y, nodes, str) => { // 接受xy坐标 接受这个node对象 接受拼接的str字符串
    if (nodes[board[x][y]].isEnd) { // 判断在二号个未知的饿字符是不是在这个nodes里面 并且是不是isEnd
      ret.push(str + board[x][y]) // 将其加入到结果中
      nodes[board[x][y]].isEnd = false // 改为false 以防后面再次遍历
    }
    nodes = nodes[board[x][y]] // 处理本层状态 
    str += board[x][y] // 拼接到str上
    visited[x * 100 + y] = true // 表示这个已经访问过了
    for (let [dx, dy] of dxys) {
      const newX = x + dx
      const newY = y + dy
      if (newX < 0 || newY < 0 || newX >= xLen || newY >= yLen || !nodes[board[newX][newY]] || visited[newX * 100 + newY]) {
        // 越界访问过不存在 就调过
        continue
      }
      // 否则继续下一个
      dfs(newX, newY, nodes, str)
    }
    visited[x * 100 + y] = false // 回溯设置为false
  }
  for (let x = 0; x < xLen; x++) {
    for (let y = 0; y < yLen; y++) {
      if (trie.children[board[x][y]]) dfs(x, y, trie.children, "");
    }
  }
  return ret;
};

var Trie = function () {
  this.children = {};
};
Trie.prototype.insert = function (word) {
  let nodes = this.children;
  for (const ch of word) {//循环word
    if (!nodes[ch]) {//当前字符不在子节点中 则创建一个子节点到children的响应位置
      nodes[ch] = {};
    }
    nodes = nodes[ch];//移动指针到下一个字符
  }
  nodes.isEnd = true;//字符是否结束
};